'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-10-27 16:08:39
'''
#
# @lc app=leetcode.cn id=85 lang=python3
#
# [85] 最大矩形
#

# @lc code=start
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        ans = 0
        m = len(matrix)
        n = len(matrix[0])
        left = [0]*n
        height = [0]*n
        right = [n]*n
        

        for i in range(m):
            cur_left=0
            cur_right = n
            # update the height
            for j in range(n):
                height[j] = height[j]+1 if matrix[i][j]=='1' else 0
            
            # update the left
            for j in range(n):
                left[j] = max(left[j], cur_left) if matrix[i][j]=='1' else 0 # to set 0 means from the large length, note that the height and left and right are all coherence.
                if matrix[i][j]=='0':
                    cur_left = j+1
            # update the right
            for j in range(n-1, -1, -1):
                right[j] = min(right[j], cur_right) if matrix[i][j]=='1' else n
                if matrix[i][j]=='0':
                    cur_right = j
            for j in range(n):
                ans = max(ans, height[j]*(right[j]-left[j]))
        return ans
# @lc code=end

